<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title>链表</title>
	</head>
	<body>
	</body>
</html>
<script type="text/javascript">
	// 链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同

	/*
	数组：
		要存储多个元素，数组（或称为列表）可能是最常用的数据结构。
		缺点：
			数据的常见通常需要申请一段连续的内存空间（一整块的内存），并且大小是固定的（大多数编程语言数组都是固定的），所以当当前数组不能满足容量需求是，需要扩容，（一般情况下是申请一个更大的数组，比如2倍。然后将原数组中的元素复制过去）
			
			而且在数组开头或中间位置插入数据的成本很高，需要进行大量元素的位移。
			
	链表：
		不同于数组，链表中的元素在内存中不必是连续的空间
		链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（有些语言称为指针或者连接）组成
		
		相对于数组的优点：
			内存空间不是必须连续的，可以充分利用计算机的内存，实现灵活的内存动态管理。
			链表不必再创建时就确定大小，并且大小可以无限的延伸下去。
			链表在插入和删除数据时，时间复杂度可以达到O(1)，相对数组效率高很多。
	
	**/

	// 链表的封装

	/*
	一定包含head属性
	
	常见的操作：
		append(element):向列表尾部添加一个新的项
						链表本身为空，新添加的数据是唯一的节点
						链表不为空，需要向其它节点后面追加节点
		
		insert(position,element):向列表的特定位置插入一个新的项
		get(position):获取对应位置的元素
		indexOf(element):返回元素在列表中的索引。如果列表中没有该元素则返回-1
		updata(position):修改某个位置的元素
		removeAt(position):从列表的特定位置移除一项
		remove(element):从列表中移除一项
		isEmpty():如果链表中不包含任何元素，返回true
		size():返回链表包含的元素个数，与素组的length属性类似
		toString():由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法
		让其只输出元素的值。
					还是从head开头，因为获取链表的任何元素都必须从第一个节点开头
					循环便于每一个接地，并不取出其中的element ，拼接 成字符串
	**/



	function linkeList() {
		// 内部节点类：
		function Node(data) {
			this.data = data
			this.next = null
		}
		this.length = 0;
		this.head = null; 
		// 1.追加方法
		linkeList.prototype.append = function(data) {
			// 判断是否为第一个节点
			// 1.创建新的节点
			var newNode = new Node(data)
			// 2.判断是否添加的节点是第一个节点
			if (this.length == 0) { //2.1是第一个节点
				this.head = newNode;
			} else { //2.2 不是第一个节点
				var current = this.head
				console.log('this.head', this.head)
				while (current.next) {
					current = current.next
				}
				current.next = newNode
			}
			this.length += 1
		}
		//2.toString 
		linkeList.prototype.toString = function() {
			// 1.定义变量
			var current = this.head;
			var listString = ''
			// 2.循环获取一个个节点
			while (current) {
				listString = listString + current.data + ' '
				current = current.next
			}
			return listString
		}

		// 3.insert 方法
		linkeList.prototype.insert = function(position, data) {
			// 1.对position进行越界判断
			if (position < 0 || position > this.length) return false;
			//2.根据data创建节点
			var newNode = new Node(data)
			// 3.判断插入的位置是否是第一个
			if (position == 0) {
				newNode.next = this.head
				this.head = newNode
			} else {
				var index = 0;
				var current = this.head;
				var previous = null;
				while (index++ < position) {
					previous = current;
					current = current.next
				}
				newNode.next = current
				previous.next = newNode	
			}
			// 4.length+1
			this.length += 1
			return true
		}

		// 4.get
		linkeList.prototype.get = function(position) {
			// 1.越界判断
			if (position < 0 || position >= this.length) return null;
			// 2.获取对应的数据
			var current = this.head;
			var index = 0;
			while (index++ < position) {
				current = current.next
			}
			return current.data
		}
		// 5.indexOf
		linkeList.prototype.indexOf = function(data){
			// 1.定义变量
			var current = this.head;
			var index = 0;
			
			// 2.开始查找
			while(current){
				if(current.data == data){
					return index
				}
				current=current.next
				index+=1
			}
			// 3.没有找到返回-1
			return -1
		}
		// 6.update
		linkeList.prototype.update = function(position,Newdata){
			// 1.越界判断
			if(position < 0 || position>= this.length) return false
			
			// 2.查找正确的位置
			var current = this.head
			var index = 0;
			while(index++ < position){
				current=current.next
			}
			
			// 3.将数据更新
			current.data = Newdata
			return true
			
		}
		// 7.removeAt
		linkeList.prototype.removeAt = function(position){
			// 1.越界判断
			if(position < 0 || position>= this.length) return null
			// 2.判断是否删除的是第一个节点
			var current = this.head;
			if(position == 0){
				this.head = this.head.next;
			}else{
				var index = 0;
			
				var previous = null
				while(index++ < position){
					previous=current
					current=current.next
				}
				// 前一个节点的next指向，current的next即可
				previous.next = current.next
			}
			// 3.length需要减1
			this.length -=1
			return current.data
			
		}
		// 8.remove
		linkeList.prototype.remove = function(data){
			// 1.根据data获取索引
			var position = this.indexOf(data)
			// 2.根据索引删除节点数据
			
			return  this.removeAt(position)
		}
		// 9.isEmpty
		linkeList.prototype.isEmpty = function(){
			return this.length == 0
		}
		// 10.size
		linkeList.prototype.size = function(){
			return this.length
		}
		// 11.反序
		linkeList.prototype.reveser = function(head){
			if(!head){
				return null
			}
			if(head.next == null){
                return head
            }
			var new_head=this.reveser(head.next);
            //把当前节点连接到链表上
            head.next.next=head; 
            head.next=null;
            return new_head;
			// if(!head){
            //     return null;
            // }
            // var pre_node = null;  //当前节点的前一个节点
            // var curr_node = head;//当前要翻转的节点
            // while(curr_node){
            //     var next_node = curr_node.next;//当前节点的后一个节点
            //     curr_node.next=pre_node;// 对当前节点进⾏行行翻转
            //     pre_node = curr_node;// pre_node向后滑动
            //     curr_node=next_node; // curr_node向后滑动
            // }
            // //最后要返回pre_node,当循环结束时,pre_node指向翻转前链表的最后⼀一个节点
            // return pre_node;   
		},
		// 12.当前链表
		linkeList.prototype.newList = function(){
			return this.head
		}
		
	}

	// 测试代码

	var list = new linkeList();

	//2.追加数据
	list.append('abc')
	list.append('cbd')
	list.append('def')
	// alert(list.toString())

	// list.insert(1, 'aaa')
	var c= list.newList()
	console.log('c',c)
	var d= list.reveser(c)
	console.log('d',d)

	// list.insert(2, 'bbb')
	// list.insert(6, 'ddd')
	// alert(list.toString())
	
	// // 
	// alert(list.indexOf('aaa'))
	// alert(list.indexOf('bbb'))
	// alert(list.indexOf('21321'))
	
	// alert(list.update(0,'fff'))
	// alert(list.toString())
	
	// // 
	// alert(list.removeAt(0))
	// alert(list.removeAt(3))
	// alert(list.toString())
</script>
